package linkedlist;

import org.junit.Test;

public class SortList148 {

    @Test
    public void test() {
        ListNode list1 = ListNode.buildList(1);
        ListNode.printList(sortList(list1), "1");

        list1 = ListNode.buildList(1, 2);
        ListNode.printList(sortList(list1), "2");

        list1 = ListNode.buildList(2, 1);
        ListNode.printList(sortList(list1), "3");

        list1 = ListNode.buildList(1, 2, 3);
        ListNode.printList(sortList(list1), "4");

        list1 = ListNode.buildList(3, 1, 2);
        ListNode.printList(sortList(list1), "5");

        list1 = ListNode.buildList(3, 2, 1);
        ListNode.printList(sortList(list1), "6");
    }

    // use merge sort from size 1 to N/2
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListRange range = sortListBeforeEnd(head, null);
        return range.first;
    }

    // return [head, last]
    public ListRange sortListBeforeEnd(ListNode first, ListNode end) {
        if (first.next == end) {
            return new ListRange(first, first);
        }
        ListNode fast = first;
        ListNode slow = first;
        while (fast != end && fast.next != end && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果有奇数个节点: fast=最后节点, slow=正中间节点
        // 如果有偶数个节点: fast=end或null, slow=后半段起始节点
        ListRange range1 = sortListBeforeEnd(first, slow);
        ListRange range2 = sortListBeforeEnd(slow, end);
        return mergeSortRanges(range1, range2);
    }

    public ListRange mergeSortRanges(ListRange range1, ListRange range2) {
        ListNode node1 = range1.first;
        ListNode node2 = range2.first;
        ListNode dummyHead = new ListNode();
        ListNode curr = dummyHead;
        while (node1 != range1.last.next && node2 != range2.last.next) {
            if (node1.val < node2.val) {
                curr.next = node1;
                node1 = node1.next;
            } else {
                curr.next = node2;
                node2 = node2.next;
            }
            // 不要忘了后移一位
            curr = curr.next;
        }
        ListNode rest = (node1 != range1.last.next) ? node1 : node2;
        ListNode restLast = (node1 != range1.last.next) ? range1.last : range2.last;

        while (rest != restLast.next) {
            curr.next = rest;
            rest = rest.next;
            // 不要忘了后移一位, 很容易忘, shit
            curr = curr.next;
        }
        // 不要忘了将尾部置为null, 否则会引起循环.
        curr.next = null;
        return new ListRange(dummyHead.next, curr);
    }

    static class ListRange {
        ListNode first; // included
        ListNode last;  // included

        public ListRange(ListNode first, ListNode last) {
            this.first = first;
            this.last = last;
        }

        @Override
        public String toString() {
            return String.format("[%s, %s]", first.val, last.val);
        }
    }
}
